1. Field of the Invention
This invention relates to data communications over a network of unknown trustworthiness.
2. Description of the Related Art
To date, routing protocols that consider adversarial networks have been of two main flavors. End-to-End Communication protocols consider dynamic topologies. Fault Detection and Localization protocols handle devious behavior of nodes.
One example addressing End-to-End Communication in distributed networks is the Slide protocol, also know as “gravitational flow” routing. It was designed to perform end-to-end communication with bounded memory in a model where an adversary controls the links between nodes in the network. There has been much work based on the Slide protocol. For example, see Y. Afek, E. Gafni “End-to-End Communication in Unreliable Networks.” PODC, pp. 1988; Y. Afek, B. Awebuch, E. Gafni, Y. Mansour, A. Rosen, and N. Shavit. “Slide—The Key to Polynomial End-to-End Communication.” Journal of Algorithms 22, pp. 158-186, 1997; B. Awerbuch, Y Mansour, N Shavit “End-to-End Communication With Polynomial Overhead.” Proc. of the 30th IEEE Symp. on Foundations of Computer Science, FOCS, 1989; and E. Kushilevitz, R. Ostrovsky, and A. Rosén. “Log-Space Polynomial End-to-End Communication.” SIAM Journal of Computing 27(6): 1531-1549, 1998. However, to our knowledge, there is no prior work based on the Slide protocol that can handle malicious behavior of nodes.
There have also been a number of works that explore the possibility of a node-controlling adversary that can corrupt nodes. In one idealized model of this scenario, the adversary can corrupt any node on the path (except the sender and receiver) in a dynamic and malicious manner. Since corrupting any node on the path will sever the honest connection between the sender and receiver, the goal of a protocol in this model is not to guarantee that all messages sent to R the receiver are received. Instead, the goal is to detect faults when they occur and to localize the fault to a single edge. See for example B. Barak, S. Goldberg, and D. Xiao. “Protocols and Lower Bounds for Failure Localization in the Internet.” Proc. of Advances in Cryptology—27th EUROCRYPT 2008, Springer LNCS 4965, pp. 341-360, 2008.
One approach addressing this model uses the notion of a secured fault detection/fault localization protocol, as well as providing lower bounds in terms of a communication complexity to guarantee accurate fault detection/location in the presence of a node-controlling adversary. However, this approach does not seek to guarantee successful or efficient routing between the sender and receiver. Instead, the mathematical proof of security guarantees that if a package is deleted, malicious nodes cannot collude to convince the sender that no fault occurred, nor can they persuade the sender into believing that the fault occurred on an honest edge. Localizing the fault in this approach relies on cryptographic tools, and in particular the assumption that one-way functions exist. Although utilizing these tools increases communication cost, it has been shown that the existence of a protocol that is able to securely detect faults (in the presence of a node-controlling adversary) implies the existence of one-way functions, and it has also been shown that any protocol that is able to securely localize faults necessarily requires the intermediate nodes to have a trusted setup.
In addition to the routing protocol work described above, there has been a fair amount of work on error correction in an active setting. Due to space considerations, we will not be able to give a comprehensive account of all the work in this area. Instead we highlight some of the most relevant works. For a lengthy treatment of error-correcting codes against polynomially bounded adversaries, we refer to S. Micali, C. Peikert, M. Sudan, and D. Wilson. “Optimal Error Correction Against Computationally Bounded Noise.” TCC LNCS 3378, pp. 1-16, 2005 and references therein. However, this work deals with a graph with a single “noisy” edge, as modeled by an adversary who can partially control and modify information that crosses the edge. In particular, it does not address throughput efficiency or memory considerations in a full communication network, nor does it account for malicious behavior at the nodes. S. Rajagopalan and L. Schulman “A Coding Theorem for Distributed Computation.” Proc. 26th STOC, pp. 790-799, 1994 consider error-correcting network coding. However, their work does not consider actively malicious nodes.
The figures depict embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.